/* 0. 代码随想录 */
// step 0# 全局变量定义
char** path;                // 当前回文子串路径
int pathTop;                // path 栈顶索引
char*** ans;                // 最终结果集
int ansTop = 0;             // 结果集大小
int* ansSize;               // 每个结果中子串数量

// step 1# 将当前 path 拷贝进结果数组 ans 中
void copy() {
    // step 1.1# 创建并复制 path 中的内容
    char** tempPath = (char**)malloc(sizeof(char*) * pathTop);
    for (int i = 0; i < pathTop; i++) {
        tempPath[i] = path[i];
    }

    // step 1.2# 存储到结果集中
    ans[ansTop] = tempPath;
    ansSize[ansTop++] = pathTop;
}

// step 2# 判断 str[startIndex...endIndex] 是否是回文
bool isPalindrome(char* str, int startIndex, int endIndex) {
    while (endIndex >= startIndex) {
        if (str[endIndex--] != str[startIndex++]) return 0;
    }
    return 1;
}

// step 3# 截取字符串 str 的子串 [startIndex, endIndex]
char* cutString(char* str, int startIndex, int endIndex) {
    // step 3.1# 开辟目标字符串空间
    char* tempString = (char*)malloc(sizeof(char) * (endIndex - startIndex + 2));
    int index = 0;

    // step 3.2# 逐个复制字符
    for (int i = startIndex; i <= endIndex; i++) {
        tempString[index++] = str[i];
    }
    tempString[index] = '\0';
    return tempString;
}

// step 4# 回溯函数：寻找所有可能的回文划分路径
void backTracking(char* str, int strLen, int startIndex) {
    // step 4.1# 如果起始位置越界，说明找到一种分割方案
    if (startIndex >= strLen) {
        copy();  // 保存当前路径
        return;
    }

    // step 4.2# 尝试从 startIndex 开始的所有子串
    for (int i = startIndex; i < strLen; i++) {
        // step 4.2.1# 如果是回文，加入 path
        if (isPalindrome(str, startIndex, i)) {
            path[pathTop++] = cutString(str, startIndex, i);
        } else {
            continue;  // 非回文直接跳过
        }

        // step 4.2.2# 递归进入下一层
        backTracking(str, strLen, i + 1);

        // step 4.2.3# 回溯，弹出最后加入的字符串
        pathTop--;
    }
}

// step 5# 主函数接口：调用回溯并返回结果
char*** partition(char* s, int* returnSize, int** returnColumnSizes) {
    int strLen = strlen(s);

    // step 5.1# 初始化全局数组空间
    path = (char**)malloc(sizeof(char*) * strLen);          // 最多分成 strLen 个子串
    ans = (char***)malloc(sizeof(char**) * 40000);          // 最多 40000 组答案
    ansSize = (int*)malloc(sizeof(int) * 40000);            // 每组的子串数量
    ansTop = pathTop = 0;

    // step 5.2# 执行回溯
    backTracking(s, strLen, 0);

    // step 5.3# 设置返回值
    *returnSize = ansTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    for (int i = 0; i < ansTop; ++i) {
        (*returnColumnSizes)[i] = ansSize[i];
    }

    return ans;
}

/* 1. 20250422 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

/*
    1. 回溯的递归终止条件：遍历到末尾
    2. 加入 path 路径的条件：是回文
*/

// step 0# 全局变量定义
char ***ans;     // 保存最终所有合法回文分割的结果
char **path;     // 当前路径，保存一组中间回文子串
int *pathLen;    // 每组 path 的长度
int ansTop;      // ans 数组的当前大小
int pathTop;     // path 栈顶指针（当前路径中的子串数量）

// step 1# 截取字符串 str[start...end]
char *cutString(char *str, int start, int end) {
    int index = 0;
    // step 1.1# 分配足够空间（子串长度 + 1 个 '\0'）
    char *temp = (char *)malloc(sizeof(char) * (end - start + 2));
    
    // step 1.2# 拷贝子串内容
    for (int i = start; i <= end; i++) {
        temp[index++] = str[i];
    }
    temp[index] = '\0';  // step 1.3# 字符串结束符
    return temp;
}

// step 2# 判断一个字符串是否是回文串
bool isAns(char *str) {
    int strLen = strlen(str);
    // step 2.1# 双指针判断回文
    for (int i = 0, j = strLen - 1; i < j; i++, j--) {
        if (str[i] != str[j]) return false;
    }
    return true;
}

// step 3# 回溯函数，寻找所有合法分割路径
void backtracking(char *str, int strLen, int startIndex) {
    // step 3.1# 终止条件：已经遍历完整个字符串
    if (startIndex == strLen) {
        // step 3.1.1# 拷贝当前路径 path 并加入结果集 ans
        char **temp = (char **)malloc(sizeof(char *) * pathTop);
        for (int i = 0; i < pathTop; i++) {
            temp[i] = path[i];  // 注意：这里直接引用 path[i]（已 malloc）
        }
        ans[ansTop] = temp;         // 加入总结果
        pathLen[ansTop++] = pathTop;  // 记录每组的子串数量
        return;
    }

    // step 3.2# 枚举从 startIndex 到 strLen-1 的所有子串
    for (int i = startIndex; i < strLen; i++) {
        // step 3.2.1# 截取当前子串
        char *curStr = cutString(str, startIndex, i);

        // step 3.2.2# 如果是回文，加入 path，然后递归下一层
        if (isAns(curStr)) {
            path[pathTop++] = curStr;

            // step 3.2.3# 递归探索下一个位置
            backtracking(str, strLen, i + 1);

            // step 3.2.4# 回溯，弹出当前子串
            pathTop--;
        } else {
            free(curStr);  // 非回文的子串需要释放内存
        }
    }
}

// step 4# 主函数入口：初始化、调用回溯并构造返回值
char*** partition(char* s, int* returnSize, int** returnColumnSizes) {
    // step 4.1# 分配空间
    ans = (char ***)malloc(sizeof(char **) * 40000);  // 最多 40000 组答案
    path = (char **)malloc(sizeof(char *) * 40000);   // 最多 40000 个子串路径
    pathLen = (int *)malloc(sizeof(int) * 40000);     // 每组路径长度
    ansTop = pathTop = 0;

    // step 4.2# 获取字符串长度并调用回溯
    int size = strlen(s);
    backtracking(s, size, 0);

    // step 4.3# 构造返回值
    *returnSize = ansTop;
    *returnColumnSizes = (int *)malloc(sizeof(int) * ansTop);
    for (int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = pathLen[i];  // 每组结果中的子串数量
    }

    return ans;
}

/* 2. 20250424 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
/*
    step 1# 问题转化：将字符串切分为多个子串，使每个子串都是回文
    step 2# 递归参数：s（原始字符串），startIndex（当前递归起点）
    step 3# 终止条件：startIndex >= strlen(s)，表示所有字符已处理完
    step 4# 单层逻辑：
        - 从 startIndex 向后枚举子串
        - 判断是否为回文
        - 是则加入 path，递归下一段
        - 否则跳过
*/

char ***ans;      // step 0.1# 最终返回的结果数组（3D）
int ansTop;       // step 0.2# 当前结果数组大小（答案个数）
char **path;      // step 0.3# 当前路径（保存某种分割方式）
int pathTop;      // step 0.4# 当前路径长度
int *ansLen;      // step 0.5# 每个答案中 path 的长度（列大小）

// step 5# 截取字符串 s[start:end]，返回一个新堆区字符串
char *cutString(char *originStr, int start, int end) {
    int subStringCount = 0;
    char *subString = (char *)malloc(sizeof(char) * (end - start + 2));
    for (int i = start; i <= end; i++) {
        subString[subStringCount++] = originStr[i];
    }
    subString[subStringCount] = 0;
    return subString;
}

// step 6# 判断某字符串是否为回文串
bool isValid(char *originStr) {
    int left = 0;
    int right = strlen(originStr) - 1;
    for (; left <= right; left++, right--) {
        if (originStr[left] != originStr[right]) {
            return false;
        }
    }
    return true;
}

// step 7# 主回溯函数
void backtracking(char *s, int startIndex) {
    // step 7.1# 终止条件：遍历完所有字符
    if (startIndex >= strlen(s)) {
        if (pathTop > 0) {
            // step 7.2# 保存当前路径到答案中
            int tempCount = 0;
            char **temp = (char **)malloc(sizeof(char *) * pathTop);
            for (int i = 0; i < pathTop; i++) {
                temp[tempCount++] = path[i];  // 复制路径
            }
            ans[ansTop] = temp;
            ansLen[ansTop++] = pathTop;       // 记录路径长度
        }
        return;
    }

    // step 7.3# 枚举所有可能的切割位置
    for (int i = startIndex; i < strlen(s); i++) {
        char *subString = cutString(s, startIndex, i);      // step 7.3.1# 获取子串

        if (isValid(subString)) {                           // step 7.3.2# 是回文则处理
            path[pathTop++] = subString;                    // 加入路径
            backtracking(s, i + 1);                         // 递归后续部分
            pathTop--;                                      // 回溯：移除最后加入的元素
        } else {
            free(subString);                                // step 7.3.3# 非回文，释放内存
        }
    }
}

// step 8# 主函数：分配空间并调用回溯入口
char*** partition(char* s, int* returnSize, int** returnColumnSizes) {
    // step 8.1# 初始化全局变量和内存分配
    path = (char **)malloc(sizeof(char *) * 40000);
    ans = (char ***)malloc(sizeof(char **) * 40000);
    ansLen = (int *)malloc(sizeof(int) * 40000);
    pathTop = ansTop = 0;

    // step 8.2# 启动回溯
    backtracking(s, 0);

    // step 8.3# 填写返回值
    *returnSize = ansTop;
    *returnColumnSizes = (int *)malloc(sizeof(int) * ansTop);
    for (int i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = ansLen[i];
    }

    return ans;
}
